import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution969 {
    public List<Integer> pancakeSort(int[] arr) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<arr.length;i++){
            map.put(arr[i],i);
        }
        List<Integer> list=new ArrayList<>();
        for (int i=arr.length-1;i>=0;i--){
            int t=map.get(i+1);
            if (t!=i){
                if (t!=0) {
                    list.add(t+1);
                    reverse(t, arr, map);
                }
                list.add(i+1);
                reverse(i,arr,map);
            }
        }
        return list;
    }

    private void reverse(int t, int[] arr, Map<Integer, Integer> map) {
        for (int i=0,j=t;i<j;i++,j--){
            map.put(arr[i],j);
            map.put(arr[j],i);
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution969().pancakeSort(new int[]{3,2,4,1}));
    }
}
